package 力扣.双指针.最长区间;

import 力扣.递归.至少有K个重复字符的最长子串395;

import java.util.HashMap;
import java.util.Map;

public class 第一个只出现一次的字符Offer50 {
    /**
     * 方法一：hash表实现，但是hashmap的key是乱序的，所以要找到第一个出现的则需要利用索引
     * @param s
     * @return
     */
    public char firstUniqChar(String s) {
         int N = s.length();
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            char c = s.charAt(i);
            if (!hashMap.isEmpty() && hashMap.containsKey(c)){
                hashMap.put(c, -1);
            }else {
                hashMap.put(c, i);//将字符和索引一起存入hashmap中
            }
        }
        int ans = N;
        for (Map.Entry<Character,Integer> entry : hashMap.entrySet()) {
            if (entry.getValue() != -1){
                if (entry.getValue() < ans){//选择只出现一次的并且索引最小的
                    ans = entry.getValue();
                }
            }
        }
        return ans == N ? ' ' : s.charAt(ans);
    }

    /**
     * 字典树
     * 遍历字符串，使用数组记录每一个字符出现的次数
     * 然后重新遍历字符串，按照字符串的顺序从数组的寻找只出现一次的字符
     *
     * 千万不要从数组中遍历，因为字符的出现顺序只和字符串有关
     */
    public char firstUniqChar2(String s) {
          int[] pos = new int[26];
          int N = s.length();
        for (int i = 0; i < N; i++) {
            char c = s.charAt(i);
            pos[c - 97]++;
        }
        for (int i = 0; i < N; i++) {//遍历字符串
            char c = s.charAt(i);
            if (pos[c - 97] == 1){
                return c;
            }
        }
        return ' ';
    }

}
